#include<stdio.h>
#include<malloc.h>

typedef struct treeNode_t
{
    struct treeNode_t *parent;
    struct treeNode_t *lNode;
    struct treeNode_t *rNode;
    int data;
} treeNode_t;

const int nodeSize = sizeof(treeNode_t);

void insert(treeNode_t * root, int val)
{
    treeNode_t * p = root;
    treeNode_t ** dir = NULL;

    while (1)
    {
        if(p->data < val)
            dir = &(p->lNode);
        else 
            dir = &(p->rNode);
        
        if(*dir == NULL)
        {
            *dir = (treeNode_t *) malloc(nodeSize);
            if(*dir == NULL)
            {
                perror("Allocation fail.\n");
                return ;
            }
            
            **dir = (treeNode_t){
                p,
                NULL,
                NULL,
                val
            };
            return;
        }
        else 
        {
            p = *dir;
        }
    }
}

void preorderTravese(treeNode_t *root)
{
    treeNode_t* stack[10000];

    int i = 0;

    stack[i] = root;
    ++ i;
    
    while (i != 0)
    {
        treeNode_t * ref = stack[i-1];
        -- i;


        printf("%d ", ref->data);


        if(ref->rNode != NULL)
        {
            stack[i] = ref->rNode;
            ++ i;
        }

        if(ref->lNode != NULL)
        {
            stack[i] = ref->lNode; 
            ++ i;
        }
    }
}


void midorderTravese(treeNode_t *root)
{
    // current node
    treeNode_t* stack[10000];
    // current action
    char actionstack[10000];
    int i = 0;

    stack[i] = root;
    actionstack[i] = 'l';
    ++ i;
    
    while (i != 0)
    {
        treeNode_t * ref = stack[i-1];

        if(actionstack[i-1] == 'l')
        {
            // self <- r
            actionstack[i-1] = 'r';

            if(ref->lNode != NULL)
            {
                // push as l 
                stack[i] = ref->lNode;
                actionstack[i] = 'l';
                ++ i;  
            }
        } 
        else 
        {
            -- i;   // pop

            printf("%d ", ref->data); // visit

            if(ref->rNode != NULL)
            {
                // push as l
                stack[i] = ref->rNode;
                actionstack[i] = 'l';
                ++ i; 
            }
        }

    }
    
}


void postorderTravese(treeNode_t *root)
{
    // current node
    treeNode_t* stack[10000];
    // current action
    char actionstack[10000];
    int i = 0;

    stack[i] = root;
    actionstack[i] = 'l';
    ++ i;
    
    while (i != 0)
    {
        treeNode_t * ref = stack[i-1];
        
        if(actionstack[i-1] == 'l')
        {
            // self <- r
            actionstack[i-1] = 'r';

            if(ref->lNode != NULL)
            {
                // push as l 
                stack[i] = ref->lNode;
                actionstack[i] = 'l';
                ++ i;  
            }
        } 
        else if(actionstack[i-1] == 'r')
        {

            // self <- mid
            actionstack[i-1] = 'm';

            if(ref->rNode != NULL)
            {
                // push as l
                stack[i] = ref->rNode;
                actionstack[i] = 'l';
                ++ i; 
            }
        } 
        else 
        {
            // pop
            -- i; 

            printf("%d ", ref->data); // visit
        }

    }
}


void styleOut(treeNode_t *root)
{
    // current node
    treeNode_t* stack[10000];
    // current action
    char actionstack[10000];
    int i = 0;

    stack[i] = root;
    actionstack[i] = 'l';
    ++ i;
    
    while (i != 0)
    {
        treeNode_t * ref = stack[i-1];

        if(actionstack[i-1] == 'l')
        {
            printf("( ");

            // self <- r
            actionstack[i-1] = 'm';

            if(ref->lNode != NULL)
            {
                // push as l 
                stack[i] = ref->lNode;
                actionstack[i] = 'l';
                ++ i;  
            }
            else 
            {
                printf("( NULL )");
            }
        } 
        else if(actionstack[i-1] == 'm')
        {

            printf("%d", ref->data); // visit

            actionstack[i-1] = 'r';

            if(ref->rNode != NULL)
            {
                // push as l
                stack[i] = ref->rNode;
                actionstack[i] = 'l';
                ++ i; 
            } 
            else 
            {
                printf("( NULL )");
            }
        }
        else 
        {
            -- i;

            printf(" )");
        }

    }
    
}


int main(int argc, char *argv[])
{
    treeNode_t *root = (treeNode_t*)malloc(nodeSize);
    *root = (treeNode_t){
        NULL,
        NULL,
        NULL,
        0
    };

    if(root == NULL) 
    {
        return -1;
    }
    
    unsigned int n;

    while(scanf("%u", &n) != 1) {}
    
    for(unsigned int i = 0; i < n; ++ i)
    {
        int v;
        while( scanf("%d",&v) != 1)
        {
            printf("Fail, please retry.\n");
        }
        if(i == 0)
        {
            root->data = v;
        }
        else
        {
            insert(root,v);
        }
    }

    printf("Tree:\n");
    styleOut(root);

    printf("\nPre-Order Travese:\n");
    preorderTravese(root);

    printf("\nMid-Order Travese:\n");
    midorderTravese(root);

    printf("\nPost-Order Travese:\n");
    postorderTravese(root);


    return 0;
}